#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAXSTRLEN 255 // 串的最大长度

typedef struct
{
    char ch[MAXSTRLEN + 1]; // 存储字符数组（0位置不使用）
    int length;             // 串的实际长度
} SString;

// 1. 初始串
bool StrAssign(SString &T, const char *chars)
{
    int len = 0;
    const char *p = chars;

    // 计算chars长度
    while (*p != '\0' && len < MAXSTRLEN)
    {
        len++;
        p++;
    }

    if (len == 0 || len > MAXSTRLEN)
    {
        return false; // 空串或超长
    }

    // 复制字符（从1位置开始存储）
    for (int i = 1; i <= len; i++)
    {
        T.ch[i] = chars[i - 1];
    }
    T.ch[len + 1] = '\0'; // 添加结束符（可选）
    T.length = len;
    return true;
}

// 2. 销毁串（顺序串无需特殊销毁）
void DestroyString(SString &S)
{
    S.length = 0; // 长度置0即可
}

// 3. 复制串
bool StrCopy(SString &T, SString S)
{
    if (S.length == 0 || S.length > MAXSTRLEN)
    {
        return false;
    }

    for (int i = 1; i <= S.length; i++)
    {
        T.ch[i] = S.ch[i];
    }
    T.length = S.length;
    return true;
}

// 4. 拼接串
bool Concat(SString &T, SString S1, SString S2)
{
    if (S1.length + S2.length > MAXSTRLEN)
    {
        return false; // 超过最大长度
    }

    // 复制S1
    for (int i = 1; i <= S1.length; i++)
    {
        T.ch[i] = S1.ch[i];
    }
    // 复制S2
    for (int i = 1; i <= S2.length; i++)
    {
        T.ch[S1.length + i] = S2.ch[i];
    }

    T.length = S1.length + S2.length;
    return true;
}

// 5. 求子串
bool SubString(SString &Sub, SString S, int pos, int len)
{
    if (pos < 1 || pos > S.length || len < 0 || pos + len - 1 > S.length)
    {
        return false; // 参数不合法
    }

    for (int i = 1; i <= len; i++)
    {
        Sub.ch[i] = S.ch[pos + i - 1];
    }
    Sub.length = len;
    return true;
}

// 6. 朴素模式匹配（定位子串位置）
int Index(SString S, SString T)
{
    if (T.length == 0 || S.length < T.length)
    {
        return -1; // 空串或主串比子串短
    }

    int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (S.ch[i] == T.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 2; // i回溯到上次开始位置的下一位
            j = 1;         // j重置为1
        }
    }

    if (j > T.length)
    {
        return i - T.length; // 匹配成功，返回位置
    }
    return -1; // 匹配失败
}

// 7. 比较串
int StrCompare(SString S, SString T)
{
    int minLen = (S.length < T.length) ? S.length : T.length;

    for (int i = 1; i <= minLen; i++)
    {
        if (S.ch[i] != T.ch[i])
        {
            return S.ch[i] - T.ch[i];
        }
    }
    return S.length - T.length; // 前缀相同，比较长度
}

// 8. 判空
bool StrEmpty(SString S)
{
    return (S.length == 0);
}

// 9. 求串长
int StrLength(SString S)
{
    return S.length;
}

// 打印串内容
void PrintString(SString S)
{
    if (StrEmpty(S))
    {
        printf("String is empty\n");
        return;
    }

    printf("String: ");
    for (int i = 1; i <= S.length; i++)
    {
        printf("%c", S.ch[i]);
    }
    printf("\n");
}

int main()
{
    SString S, T, U, Sub;

    // 初始串
    StrAssign(S, "Hello");
    StrAssign(T, "World");
    PrintString(S); // String: Hello

    // 复制串
    StrCopy(U, S);
    PrintString(U); // String: Hello

    // 拼接串
    Concat(U, S, T);
    PrintString(U); // String: HelloWorld

    // 求子串
    SubString(Sub, U, 3, 5);
    PrintString(Sub); // String: lloWo

    // 模式匹配
    int pos = Index(U, T);
    printf("'World' position: %d\n", pos); // 'World' position: 6

    // 比较串
    SString A, B;
    StrAssign(A, "apple");
    StrAssign(B, "banana");
    printf("Compare: %d\n", StrCompare(A, B)); // 负数（a<b）

    // 判空
    printf("S empty? %s\n", StrEmpty(S) ? "true" : "false");

    // 求长度
    printf("Length of U: %d\n", StrLength(U)); // 10

    DestroyString(S);
    DestroyString(T);
    DestroyString(U);
    return 0;
}